import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
class Solution {
    boolean[][] visited;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        visited = new boolean[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 1){
                    queue.offer(new int[]{i, j});
                    grid[i][j] = 0;
                    visited[i][j] = true;
                }

        //BFS
        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            int distance = grid[poll[0]][poll[1]];
            for(int k = 0; k < 4; k++){
                int x = poll[0] + dx[k];
                int y = poll[1] + dy[k];
                if(x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 && !visited[x][y]){
                    grid[x][y] = distance + 1;
                    queue.offer(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
        }

        //  遍历找出最大的距离
        int ret = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] > ret) ret = grid[i][j];

        return ret == 0 ? -1 : ret;
    }
}